Wilson's theorem

In mathematics, Wilson's theorem states that a natural number n > 1 is a prime number if and only if

(n-1)!\ \equiv\ -1 \pmod n

(see factorial and modular arithmetic for the notation).

Contents

History

The theorem was known to Ibn al-Haytham (also known as Alhazen) in circa 1000 AD,[1] but it is named after John Wilson (a student of the English mathematician Edward Waring) who stated it in the 18th century.[2] Waring announced the theorem in 1770, although neither he nor Wilson could prove it. Lagrange gave the first proof in 1771.[3] There is evidence that Leibniz was also aware of the result a century earlier, but he never published it.[4]

Proofs

First proof

If p is composite, then its positive divisors are among the integers 1, 2, 3, 4, … , p − 1 and it is clear that gcd((p − 1)!, p) > 1, so we can not have (p − 1)! ≡ −1 (mod p).

However if p is prime, then each of the above integers are relatively prime to p. It is easy to check the result when p is 2 or 3, so let us assume p > 3. So for each of these integers a there is another b such that ab ≡ 1 (mod p). It is important to note that this b is unique modulo p, and that since p is prime, a ≡ b if and only if a is 1 or p − 1. Now if we omit 1 and p − 1, then the others can be grouped into pairs whose product is 1 showing 2.3.4.….(p − 2) ≡ 1 (mod p)or more simply (p − 2)! ≡ 1 (mod p)). Finally, multiply this equality by p − 1 to complete the proof. For example, if p ≡ 11, we have

10! = 1(10)(2\cdot6)(3\cdot4)(5\cdot9)(7\cdot8) \equiv -1 \pmod{11}.\,

The commutative and associative properties are used in above procedure. All elements in the above product will be of the form g g −1 ≡ 1 (mod p) except 1 (p − 1) which is left.

If p = 2, the result is trivial to check.

To prove the converse (see below for a more exact converse result), suppose the congruence holds for a composite n, and note that then n has a proper divisor d with 1 < d < n. Clearly, d divides (n − 1)!. But by the congruence, d also divides (n − 1)! + 1, so that d divides 1, a contradiction.

Second proof

Here is another proof of the first direction: the result is clearly true for p = 2, so suppose p is a prime greater than 2 (and therefore odd). Consider the polynomial

g(x)=(x-1)(x-2) \cdots (x-(p-1)).\,

From Lagrange's theorem, if f(x) is a nonzero polynomial of degree d over a field F, then f(x) has at most d roots over F. Now, with g(x) as above, consider the polynomial

f(x)=g(x)-(x^{p-1}-1).\,

Since the leading coefficients cancel, we see that f(x) is a polynomial of degree at most p − 2. Reducing mod p, we see that f(x) has at most p − 2 roots mod p. But by Fermat's little theorem, each of the elements 1, 2, ..., p − 1 is a root of f(x). This is impossible, unless f(x) is identically zero mod p, i.e. unless each coefficient of f(x) is divisible by p.

But since p is odd, the constant term of f(x) is just (p − 1)! + 1, and the result follows.

Applications

Wilson's theorem is useless as a primality test in practice, since computing (n − 1)! modulo n for large n is hard, and far easier primality tests are known (indeed, even trial division is considerably more efficient).

Using Wilson's Theorem, for any odd prime p = 2m + 1 we can rearrange the left hand side of

1\cdot 2\cdots (p-1)\ \equiv\ -1\ \pmod{p}

to obtain the equality

1\cdot(p-1)\cdot 2\cdot (p-2)\cdots m\cdot (p-m)\ \equiv\ 1\cdot (-1)\cdot 2\cdot (-2)\cdots m\cdot (-m)\ \equiv\ -1 \pmod{p}.

This becomes

\prod_{j=1}^m\ j^2\ \equiv(-1)^{m%2B1} \pmod{p}.

We can use this fact to prove part of a famous result: for any prime p such that p ≡ 1 (mod 4) the number (−1) is a square (quadratic residue) mod p. For suppose p = 4k + 1 for some integer k. Then we can take m = 2k above, and we conclude that

\biggl( \prod_{j=1}^{2k}\ j \biggr)^{2} = \prod_{j=1}^{2k}\ j^2\ \equiv (-1)^{2k%2B1}\ = -1 \pmod{p}.

Wilson's theorem has been used to construct formulas for primes, but they are too slow to have practical value.

Generalizations

A simple generalization

Wilson's theorem can be generalized to the following statement:

\forall n\in\mathbb{N}: (n-1)! \equiv \begin{cases} -1 \pmod n & \gets n \text{ is prime} \\ 2 \pmod n & \gets n=4 \\ 0 \pmod n & \text{otherwise} \end{cases}

From the above proofs we already know that for prime n we have (n − 1)! ≡ −1 (mod n).

We can easily verify the case n = 4 (note that n = 1 must be excluded because −1 ≡ 0 (mod n) creates ambiguity in the statement). Which leaves us with the case where n is a composite number larger than 5. In this case the above statement claims that n divides (n − 1)!. We will now prove this.

Note that by definition

(n-1)! = 1\times 2 \times \cdots \times (n-1).

We will show that we can always find two of these n − 1 terms such that their product is divisible by n.

In most cases, a composite n > 5 has a divisor a such that 2 ≤ a < (n/a). In such case, the two terms are a and (n/a). The only case when no such a exists is if n is a square of a prime p > 2. In this case, the two terms are p and 2p.

Gauss's generalization

The following is a stronger generalization of Wilson's theorem, due to Carl Friedrich Gauss:

\prod_{k = 1 \atop (k,m)=1}^{m} \!\!k \ \equiv \ \left \{ \begin{matrix} \ \ 0 \pmod{m} & \text{if } m=1 \\ -1 \pmod{m} & \text{if } m=4,\;p^\alpha,\;2p^\alpha \\ \ \ 1 \pmod{m} & \text{otherwise} \end{matrix} \right.

where p is an odd prime, and \alpha is a positive integer. This further generalizes to the fact that in any finite abelian group, either the product of all elements is the identity, or there is precisely one element a of order 2. In the latter case, the product of all elements equals a.

See also

Notes

  1. ^ O'Connor, John J.; Robertson, Edmund F., "Abu Ali al-Hasan ibn al-Haytham", MacTutor History of Mathematics archive, University of St Andrews, http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Haytham.html .
  2. ^ Edward Waring, Mediationes Algebraicae (Cambridge, England: 1770), page 218 (in Latin). In the third (1782) edition of Waring's Mediationes Algebraicae, Wilson's theorem appears as problem 5 on page 380. On that page, Waring states: "Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger." (A man most illustrious and most skilled in mathematics, Squire John Wilson, found this most elegant property of prime numbers.)
  3. ^ Joseph Louis Lagrange, "Demonstration d'un théorème nouveau concernant les nombres premiers" (Proof of a new theorem concerning prime numbers), Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres (Berlin), vol. 2, pages 125–137 (1771).
  4. ^ Giovanni Vacca (1899) "Sui manoscritti inediti di Leibniz" (On unpublished manuscripts of Leibniz), Bollettino di bibliografia e storia delle scienze matematiche ... (Bulletin of the bibliography and history of mathematics), vol. 2, pages 113-116; see page 114 (in Italian). Vacca quotes from Leibniz's mathematical manuscripts kept at the Royal Public Library in Hanover (Germany), vol. 3 B, bundle 11, page 10:

    Original : Inoltre egli intravide anche il teorema di Wilson, come risulta dall'enunciato seguente:

    "Productus continuorum usque ad numerum qui antepraecedit datum divisus per datum relinquit 1 (vel complementum ad unum?) si datus sit primitivus. Si datus sit derivativus relinquet numerum qui cum dato habeat communem mensuram unitate majorem."

    Egli non giunse pero a dimostrarlo.

    Translation : In addition, he [Leibniz] also glimpsed Wilson's theorem, as shown in the following statement:

    "The product of all integers preceding the given integer, when divided by the given integer, leaves 1 (or the complement of 1?) if the given integer be prime. If the given integer be composite, it leaves a number which has a common factor with the given integer [which is] greater than one."

    However, he didn't succeed in proving it.

    See also: Guiseppe Peano, ed., Formulaire de mathématiques, vol. 2, no. 3, page 85 (1897).

References

External links